package com.origin.niuke.tree;

import general_class.TreeNode;

/**
 * NC84 完全二叉树结点数
 * 算法：深度优先搜索
 * 完全二叉树：树的叶子节点在最后一层或者倒数第二层
 * 有两种情况
 * 1、左子树和右子树的深度一样, 左子树一定是满二叉树, 右子树是满二叉树或完全二叉树
 * 2、左子树的深度大于右子树, 右子树一定是满二叉树, 左子树是满二叉树或完全二叉树
 * 满二叉树求节点数量公式: 2 ^ height - 1
 *
 * @author yezh
 * @version 1.0
 * @date 2022/11/10 22:55
 */
public class NC84 {

    public int nodeNum(TreeNode head) {
        if (head == null) return 0;
        int lh = getHeight(head.left), rh = getHeight(head.right);
        // 根节点 + 左子树的数量 + 右子树的数量
        if (lh == rh) return 1 + (1 << lh) - 1 + nodeNum(head.right);
        else return 1 + nodeNum(head.left) + (1 << rh) - 1;
    }

    int getHeight(TreeNode node) {
        int h = 0;
        while (node != null) {
            ++h;
            node = node.left;
        }
        return h;
    }

}
